% Copyright 2004 by Till Tantau <tantau@users.sourceforge.net>.
%
% In principle, this file can be redistributed and/or modified under
% the terms of the GNU Public License, version 2.
%
% However, this file is supposed to be a template to be modified
% for your own needs. For this reason, if you use this file as a
% template and not specifically distribute it as part of a another
% package/program, I grant the extra permission to freely copy and
% modify this file as you see fit and even to delete this copyright
% notice. 

\documentclass[12pt]{beamer}
% Replace the \documentclass declaration above
% with the following two lines to typeset your 
% lecture notes as a handout:
%\documentclass{article}
%\usepackage{beamerarticle}
\usepackage[utf8]{inputenc}
\usepackage[noend]{algpseudocode}
\usepackage[T1]{fontenc}
\usepackage{algorithmicx}
\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{graphicx}

\setbeamertemplate{footline}{\scriptsize{\vspace*{0cm}\hspace*{0.5cm} \insertframenumber/\inserttotalframenumber}}

% There are many different themes available for Beamer. A comprehensive
% list with examples is given here:
% http://deic.uab.es/~iblanes/beamer_gallery/index_by_theme.html
% You can uncomment the themes below if you would like to use a different
% one:
%\usetheme{AnnArbor}
%\usetheme{Antibes}
%\usetheme{Bergen}
%\usetheme{Berkeley}
%\usetheme{Berlin}
%\usetheme{Boadilla}
%\usetheme{boxes}
%\usetheme{CambridgeUS}
%\usetheme{Copenhagen}
\usetheme{Darmstadt}
%\usetheme{default}
%\usetheme{Frankfurt}
%\usetheme{Goettingen}
%\usetheme{Hannover}
%\usetheme{Ilmenau}
%\usetheme{JuanLesPins}
%\usetheme{Luebeck}
%\usetheme{Madrid}
%\usetheme{Malmoe}
%\usetheme{Marburg}
%\usetheme{Montpellier}
%\usetheme{PaloAlto}
%\usetheme{Pittsburgh}
%\usetheme{Rochester}
%\usetheme{Singapore}
%\usetheme{Szeged}
%\usetheme{Warsaw}

\title{Visualisation et Analyse des Grands Graphes}

\author{Présentateur : Nguyen Quoc Khai\\ Encadreur : Ho Tuong Vinh\\ L'auteur : M.Kwan \& M.Chris}
% - Give the names in the same order as the appear in the paper.
% - Use the \inst{?} command only if the authors have different
%   affiliation.
\date{IFI, Hanoi, 2014}
% - Either use conference name or its abbreviation.
% - Not really informative to the audience, more for people (including
%   yourself) who are reading the slides online

\subject{Theoretical Computer Science Graph}
% This is only inserted into the PDF information catalog. Can be left
% out. 

% If you have a file called "university-logo-filename.xxx", where xxx
% is a graphic format that can be processed by latex or pdflatex,
% resp., then you can add a logo as follows:

% \pgfdeclareimage[height=0.5cm]{university-logo}{university-logo-filename}
% \logo{\pgfuseimage{university-logo}}

% Delete this, if you do not want the table of contents to pop up at
% the beginning of each subsection:
\AtBeginSubsection[]
{
  \begin{frame}<beamer>{Plan de présentation}
    \tableofcontents[currentsection,currentsubsection]
  \end{frame}
}

% Let's get started
\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}{Plan de présentation}
  \tableofcontents
  % You might wish to add the option [pausesections]
\end{frame}

% Section and subsections will appear in the presentation overview
% and table of contents.
\section{Rappelle du sujet}

%\subsection{Contexte}
\begin{frame}{Contexte}
\begin{itemize}
\item Les graphes sont beaucoup utilisés
\item Les chercheurs veulent souvent faire l'analyse sur des graphes
\item Pour être facile d'analyser des graphes, on a besoin de les visualiser, les simplifier
\end{itemize}
\end{frame}

%\subsection{Visualisation du graphe}

\begin{frame}{Visualisation du graphe}
\begin{figure}[!htb]
\minipage{0.25\textwidth}
  \includegraphics[width=\linewidth]{images/g1.png}
  %\caption{Détection non seuil}\label{fig:awesome_image1}
\endminipage\hfill
\minipage{0.25\textwidth}
  \includegraphics[width=\linewidth]{images/g2.png}
  %\caption{Détection avec le seuil non érosion ni dilatation}\label{fig:awesome_image2}
\endminipage\hfill
\minipage{0.25\textwidth}
  \includegraphics[width=\linewidth]{images/g3.png}
  %\caption{Détection avec seuil, érosion et dilatation}\label{fig:awesome_image3}
\endminipage\hfill
\caption{Graphe statique\footnote{Graphe fixe des arc ou/et des vertex au cours du temps}}
\end{figure}
\begin{figure}[ht!]
\centering
\includegraphics[width=60mm]{images/g4.png}
\caption{Graphe dynamique\footnote{Graphe change des arcs ou/et vertex au cours du temps}}
\label{overflow}
\end{figure}
\end{frame}

\begin{frame}{Amélioration de visualisation}
\begin{figure}[!htb]
\minipage{0.3\textwidth}
  \includegraphics[width=\linewidth]{images/g3.png}
  %\caption{Détection non seuil}\label{fig:awesome_image1}
\endminipage\hfill
\minipage{0.3\textwidth}
  \includegraphics[width=\linewidth]{images/arrow1.png}
  %\caption{Détection avec le seuil non érosion ni dilatation}\label{fig:awesome_image2}
\endminipage\hfill
\minipage{0.3\textwidth}
  \includegraphics[width=\linewidth]{images/g11.png}
  %\caption{Détection avec seuil, érosion et dilatation}\label{fig:awesome_image3}
\endminipage\hfill
\end{figure}

\begin{figure}[!htb]
\minipage{0.3\textwidth}
  \includegraphics[width=\linewidth]{images/g12.png}
  %\caption{Détection non seuil}\label{fig:awesome_image1}
\endminipage\hfill
\minipage{0.3\textwidth}
  \includegraphics[width=\linewidth]{images/arrow1.png}
  %\caption{Détection avec le seuil non érosion ni dilatation}\label{fig:awesome_image2}
\endminipage\hfill
\minipage{0.3\textwidth}
  \includegraphics[width=\linewidth]{images/g13.png}
  %\caption{Détection avec seuil, érosion et dilatation}\label{fig:awesome_image3}
\endminipage\hfill
\end{figure}
\end{frame}

%\subsection{Simplification du graphe}

% You can reveal the parts of a slide one at a time
% with the \pause command:
\begin{frame}{Simplification du graphe}
\begin{figure}[!htb]
\minipage{0.23\textwidth}
  \includegraphics[width=\linewidth]{images/g5.png}
  %\caption{Détection non seuil}\label{fig:awesome_image1}
\endminipage\hfill
\minipage{0.23\textwidth}
  \includegraphics[width=\linewidth]{images/arrow2.png}
  %\caption{Détection avec le seuil non érosion ni dilatation}\label{fig:awesome_image2}
\endminipage\hfill
\minipage{0.23\textwidth}
  \includegraphics[width=\linewidth]{images/g6.png}
  %\caption{Détection avec seuil, érosion et dilatation}\label{fig:awesome_image3}
\endminipage\hfill
\end{figure}

\begin{figure}[!htb]
\minipage{0.23\textwidth}
  \includegraphics[width=\linewidth]{images/g7.png}
  %\caption{Détection non seuil}\label{fig:awesome_image1}
\endminipage\hfill
\minipage{0.23\textwidth}
  \includegraphics[width=\linewidth]{images/arrow2.png}
  %\caption{Détection avec le seuil non érosion ni dilatation}\label{fig:awesome_image2}
\endminipage\hfill
\minipage{0.23\textwidth}
  \includegraphics[width=\linewidth]{images/g8.png}
  %\caption{Détection avec seuil, érosion et dilatation}\label{fig:awesome_image3}
\endminipage\hfill
\end{figure}

\begin{figure}[!htb]
\minipage{0.23\textwidth}
  \includegraphics[width=\linewidth]{images/g9.png}
  %\caption{Détection non seuil}\label{fig:awesome_image1}
\endminipage\hfill
\minipage{0.23\textwidth}
  \includegraphics[width=\linewidth]{images/arrow2.png}
  %\caption{Détection avec le seuil non érosion ni dilatation}\label{fig:awesome_image2}
\endminipage\hfill
\minipage{0.23\textwidth}
  \includegraphics[width=\linewidth]{images/g10.png}
  %\caption{Détection avec seuil, érosion et dilatation}\label{fig:awesome_image3}
\endminipage\hfill
\end{figure}
\end{frame}

%\subsection{Problématiques et solutions}
\begin{frame}{Problématiques et solutions}
\begin{block}{Problématiques}
\begin{itemize}
\item Visualisation du graphe dynamique
\item Simplification du graphe
\end{itemize}
\end{block}
\begin{block}{Solution}
\begin{itemize}
\item Algorithme base sur les clusters et qui donne la prédiction des clusters de l'avenir
\item Abstraction sémantique
\end{itemize}
\end{block}
\end{frame}

\section{Visualisation du graphe}
\subsection{Graphe statique}

\begin{frame}{Visualisation du graphe statique}
\textit{Il existe beaucoup de méthode permettant de faciliter la visualisation surtout pour les grands graphes.}
\begin{block}{Meilleures positions}
\begin{itemize}
\item Une méthode de dessin basé sur les forces
\item Positionnement des nœuds d'un graphe afin de faciliter la visualisation
\item E.g : Force-directed, FM, GRIP
\end{itemize}
\end{block}
\begin{block}{Paquet des arcs}
\begin{itemize}
\item Botteler des arcs
\item Des positions des nœuds sont fixées
\item E.g : Force-directed edge bundling (FDEB)
\end{itemize}
\end{block}
\end{frame}

\begin{frame}{Méthode force-directed(FD)\cite{fd}}
\begin{figure}[ht!]
\centering
\includegraphics[width=28mm]{images/g14.png}
\label{overflow}
\end{figure}
La méthode peut être décrit comme une analogie physique des composants du graphe :
\begin{itemize}
\item Les nœuds sont représentés par des particules de même charge
\item Les arcs sont assimilables à des ressorts
\end{itemize}
\begin{block}{Algorithme SPRING(G)}
\begin{algorithmic}
\item \textit{placer aléatoire des vertex de G aux positions possible}
\While{$F \leq seuil$}
	\State \textit{Calculer la force de chaque vertex $Fi$}
	\State \textit{Déplacer vertex $Pi \gets Pi + c_4.Fi$}
\EndWhile
\item \textit{Dessin le graphe modifié}
\end{algorithmic}
\end{block}
\end{frame}

\begin{frame}{Forces de la méthode FD}
Chaque nœud a 2 types de force, supposons que $v_j$ est adjacent de $v_i$, on calcule les forces de $v_i$ :
\begin{itemize}
\item Force de Hook
\[F_{hi} = k.d\]
\item Force de Coulomb
\[F_{ci} = c.\frac{q_i.q_j}{d^2}\]
\item Force totale
\[F_i = F_{ci} + F_{hi}\]
\end{itemize}
\emph{Notes :si $F_{ci} \geq 0 $, alors $F_{hi} \leq 0 $ et l'inverse\\ k,c est un constant, d est la distance de $v_i$ à son adjacent\\
$q_i,q_j$ sont électricité}
\end{frame}

\begin{frame}{Amélioration de la méthode FD}
\begin{itemize}
\item Force de Hook $F_{hi} = c_1.log(\frac{d}{c_2})$
\item Force de Coulomb $F_{ci} = \frac{c_3}{d^2}$
\item Force totale : $F_i = F_{ci} + F_{hi}$
\end{itemize}
\emph{Notes : $c_1, c_2, c_3$ sont des constant}\\
L'auteur explique que la force de Hook classique est encore trop grande quand la distance entre 2 nœud est grande. Cette modification marche mieux.

\begin{block}{Résultat}
Avec le graphe de 30 vertex, quand l'auteur met $c_1 = 2, c_2 = 1, c_3 = 1, c_4 = 0.1, seuil$ assez petit, le système équilibré après 100 fois de répéter
\end{block}
\end{frame}

\begin{frame}{Remarques pour la méthode FD}
\begin{block}{Avantages}
\begin{itemize}
\item Facile de comprendre, respecte les lois de forces
\item Interactivité: les nœuds peuvent être replacés à la volée pendant le calcul
\end{itemize}
\end{block}
\begin{block}{Inconvénients}
\begin{itemize}
\item Ce sont des algorithmes souvent coûteux en puissance de calcul
\item Ces algorithmes souffrent pour la plupart de ne terminer que dans un état qui est un minimum local du problème d'optimisation à l'origine de la modélisation physique.
\item Pas mieux pour les grands graphes
\end{itemize}
\end{block}
\end{frame}

\begin{frame}{Méthode Force-directed edge bundling (FDEB)\cite{fdeb}}
\begin{block}{Idée :}
Botteler des arcs pendant la visualisation pour réduire la complexité du graphe.
\end{block}
\begin{block}{Méthode :}
Segmenter des arcs en N segments et chaque segment est considéré comme un ressort. Des sous vertex a des forces comme la méthode FDEB
\begin{figure}[ht!]
\centering
\includegraphics[width=40mm]{images/g15.png}
\label{overflow}
\end{figure}
\end{block}
\end{frame}

\begin{frame}{Algorithme FDEB}
\begin{algorithmic}
\For{e dans E}
	\State Diviser e en n segments;
	\For{n dans N}
		\State Calcul Fs pour n;
		\For{q dans E-e}
			\State Calcul des Fe pour n;
			\State F = Fs + Fe;
		\EndFor
		\State Déplacer n vers F;
	\EndFor
\EndFor
\end{algorithmic}
\begin{block}{Condition d'interaction en arcs}
\begin{figure}[ht!]
\centering
\includegraphics[width=90mm]{images/g17.png}
\label{overflow}
\end{figure}
\end{block}
\end{frame}

\begin{frame}{Remarques pour la méthode FDEB}
\begin{block}{Avantages}
\begin{itemize}
\item Facile de comprendre, emprunte l'idée de FD
\item Ne doit pas déplacer des vertex
\end{itemize}
\end{block}
\begin{block}{Inconvénients}
\begin{itemize}
\item Dépend le graphe entré : les vertex doivent être bien placés
\end{itemize}
\end{block}
\end{frame}

\begin{frame}{Méthode Space Filling Curves (SFC)\cite{sfc}}
\begin{block}{Exemple}
\begin{figure}[!htb]
\minipage{0.4\textwidth}
  \includegraphics[width=\linewidth]{images/g3.png}
  \caption{Graphe original}\label{fig:awesome_image1}
\endminipage\hfill
\minipage{0.4\textwidth}
  \includegraphics[width=\linewidth]{images/g11.png}
  \caption{Aplique SFC}\label{fig:awesome_image3}
\endminipage\hfill
\end{figure}
\end{block}
\end{frame}

\begin{frame}{Méthode Space Filling Curves (SFC) (2)}
\begin{figure}[ht!]
\centering
\includegraphics[width=60mm]{images/img1.png}
\label{overflow}
\end{figure}
\begin{block}{Méthode SFC}
Séparée en 3 étapes :
\begin{enumerate}
\item Création des clusters des vertex et les mettre sur les bonnes positions
\item Mise en ordre des vertex
\item Mise en SFC
\end{enumerate}
\end{block}
\end{frame}

\begin{frame}{Création des clusters}
\begin{itemize}
\item Chaque vertex est dans un cluster différent
\item Création des clusters pour maximiser $Q$
\[
Q = \frac{1}{2|V|} \sum_{i,j = 1}^{V} (a_{i,j} - \frac{d_id_j}{2|V|}) \delta(i,j)
\]
\end{itemize}
$|V|$ est le nombre de vertex\\
$a_{i,j} = 1$ si entre $i$ et $j$ est une arrête $a_{i,j} = 0$ si l'inverse\\
$d_i$ est le degré de vertex $i$\\
$\delta(i,j) = 1$ si $i$ et $j$ dans le même cluster
\end{frame}

\begin{frame}{Mise en ordre des vertex et SFC}
\begin{block}{Ordre des vertex}
Algorithme de parcours en profondeur d'abord pour l'ordre des vertex
\end{block}
\begin{block}{Mise en SFC}
\begin{itemize}
\item Une fois que les vertex sont en ordre, on les met en SFC sur l'écran pour plus belle visualiser
\item Satisfait l'équation : 
$D_{p_i,p_j} < \sqrt[c]{|i - j|}$\\
$i, j$ sont les points en $1D$ (position) sur le curve\\
$p_i, p_j$ sont les positions en $2D$ sur l'écran\\
$c$ est constant, petit
\end{itemize}
\end{block}
\end{frame}

\begin{frame}{Remarques pour la méthode SFC}
\begin{block}{Avantages}
\begin{itemize}
\item Normalement, cette méthode place bien des vertex, utilise toutes les espaces de l'écran
\item Résultat est bien malgré des grands graphes
\end{itemize}
\end{block}
\begin{block}{Inconvénients}
\begin{itemize}
\item La complexité de cette méthode est grande
\item Plus compliqué que la méthode FD
\end{itemize}
\end{block}
\end{frame}

\subsection{Graphe dynamique}

\begin{frame}{Visualisation du graphe dynamique}
\begin{block}{Principes}
\begin{itemize}
\item Facile de voir le graphe pendant chaque étape (comme les graphes statiques)
\item Stabilité du graphe au cours du temps (limiter la motion)
\end{itemize}
\end{block}
\begin{block}{Défi}
Stabilité du graphe au cours du temps
\end{block}
\begin{block}{Solution}
Algorithme base sur les clusters pour les graphes dynamiques
\end{block}
\end{frame}

\begin{frame}{Algorithme base sur les clusters\cite{dynamique_sfc}}
L'algorithme se compose de 2 parties :
\begin{enumerate}
\item Création des clusters
\item Mise en ordre des clusters et des vertex
\end{enumerate}
\end{frame}

\begin{frame}{Création des clusters}
\begin{block}{Pendant une étape de temps}
Application de la méthode SFC
\end{block}
\begin{block}{Entre des étape au cours du temps}
\begin{itemize}
\item Le graphe contient plusieurs clusters $VC = {VC_1, VC_2, ..., VC_l}$
\item $VC_i = {vc_i^1, vc_i^2, ..., vc_i^k}$ ; k est le nombre d'étape du temps
\item Cherche le cluster $vc_i^t$ le plus similaire à $vc_i^{t-1}$
\end{itemize}
\end{block}
\end{frame}

\begin{frame}{Mise en ordre des clusters}
\begin{itemize}
\item Création du graphe $QG = {V_{QG}, E_{QG}, w}$
\item Chaque vertex représente un cluster dans $VC$
\item Il y a un arête entre $VC_i$ et $VC_j \Leftrightarrow $ il y un vertex $e$ commun entre $VC_i$ et $VC_j$
\item $w_e = $nombre de vertex commun entre $VC_i$ et $VC_j$
\item Recherche d'une permutation pour minimiser la fonction : $LA_\phi(QG) = \sum_{u,v \in V_{QG}} w(uv).|p_u - p_v|$
\end{itemize}
\end{frame}

\begin{frame}{Remarques pour la méthode}
Porte l'idée de la méthode SFC
\begin{block}{Avantage}
\begin{itemize}
\item Adapté pour les graphes dynamiques
\item Connait tous les clusters de l'avenir, limite des animations
\end{itemize}
\end{block}
\begin{block}{Inconvénients}
\begin{itemize}
\item La complexité est très grande
\end{itemize}
\end{block}
\end{frame}

\section{Simplification du graphe}
\subsection{Abstraction sémantique}
\begin{frame}{Abstraction sémantique\cite{ontovis}}
\begin{itemize}
\item Un graphe sémantique est défini $G = (V, E, vt, et)$
\item Un graphe d'ontologie est défini $OG = (TV , TE)$
\item Un outil OntoVis sert à designer le graphe original
\end{itemize}
\textit{V est ensemble des vertex, E est ensemble d'arêtes\\
TV est ensemble de type des vertex, TE est ensemble de type des arêtes\\
TV = {$tv_1, tv_2, ..., tv_n$} et TE = {$te_1, te_2, ..., te_n$}\\
$tv_i = vt(v_j)$ et $te_i = et(e_j)$
}
\end{frame}

\begin{frame}{Remarques pour la méthode}
\begin{block}{Avantage}
\begin{itemize}
\item Facile d'analyser le graphe
\end{itemize}
\end{block}
\begin{block}{Limitations}
\begin{itemize}
\item Le graphe doit avoir des types différents
\item Chaque type doit avoir plusieurs vertex
\end{itemize}
\end{block}
\end{frame}

% Placing a * after \section means it will not show in the
% outline or table of contents.
\section*{Conclusion}

\begin{frame}{Conclusion}
\begin{block}{Visualisation du graphe}
\begin{itemize}
\item Visualisation du graphe statique et dynamique
\item Difficulté avec les graphes dynamique
\item Solution : SFC pour les graphes dynamiques
\end{itemize}
\end{block}
\begin{block}{Simplification du graphe}
\begin{itemize}
\item Pour analyser les graphes, les chercheurs veulent simplifier les graphes
\item Le travail actuel, pas encore des méthodes parfaites
\item Solution : Abstraction sémantique
\item Future : Diminuer la complicité des méthodes comme \textit{<<Abstraction sémantique>>}
\end{itemize}
\end{block}
\end{frame}


% All of the following is optional and typically not needed. 
%\section*{Références}

\begin{frame}[allowframebreaks]
  \frametitle<presentation>{Référence}
    
  \begin{thebibliography}{10}
    
  \beamertemplatebookbibitems
  % Start with overview books.

  \bibitem{fd}
    Stephen G. Kobourov.
    \newblock {\em Force-Directed Drawing Algorithms}.
    \newblock University of Arizona.
    
  \bibitem{fdeb}
    Danny Holten and Jarke J. van Wijk.
    \newblock {\em Force-Directed Edge Bundling for Graph}. Visualization.
    \newblock { IEEE-VGTC Symposium on Visualization, Volume 28 (2009), Number 3.}
 
  \beamertemplatearticlebibitems
  % Followed by interesting articles. Keep the list short. 

  \bibitem{sfc}
    C. Muelder and K.-L. Ma.
    \newblock {\em Rapid Graph Layout Using Space Filling Curves}.
    \newblock { IEEE Trans. Visualization and Computer Graphics, vol. 14, no. 6, 2008, pp. 1301-1308.}

  \bibitem{dynamique_sfc}
    A. Sallaberry, C.W. Muelder, and K.-L. Muelder.
    \newblock {\em Clustering, Visualizing, and Navigating for Large Dynamic Graphs}.
    \newblock {Proc. 20th Int’l Symp. Graph Drawing (GD 12), LNCS 7704, Springer, 2012, pp. 487-497.}

  \bibitem{ontovis}
    Z. Shen, K.-L. Ma, and T. Rad-Eliassi.
    \newblock {\em Visual Analysis of Large Heterogeneous Social Networks by Semantic and Structural Abstraction}.
    \newblock {IEEE Trans. Visualization and
Computer Graphics, vol. 12, no. 6, 2006, pp. 1427-1439.}

  \end{thebibliography}
\end{frame}

\begin{frame}
 \Huge Merci pour votre attention!
\end{frame}

\end{document}


